package pri.hillchen.algorithm.desgin;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by hillchen on 2017/9/29 0029.
 */
public class LRUCache<K,V> {
    class Element{
        K key;
        V value;
        Element left;
        Element rigth;

        public Element(K key,V value) {
            this.key = key;
            this.value = value;
        }
    }

    class LinkedList{
        Element head;
        Element tail;

        private Element remove(Element element){
            if(element != null){
                Element leftEle = element.left;
                Element rightEle = element.rigth;
                if(element != head && element != tail){
                    leftEle.rigth = rightEle;
                    rightEle.left = leftEle;
                }else{
                    if(element == head){
                        head = rightEle;
                        rightEle.left = null;
                    }
                    if(element == tail){
                        tail = leftEle;
                        leftEle.rigth = null;
                    }
                }
            }
            return  element;
        }

        private Element addToHead(K key,V value){
            checkLinkedList();
            Element element = new Element(key,value);
            if(head == null && tail == null){
                 head = element;
                 tail = element;
            }else if(head != null){
                element.rigth = head;
                head.left = element;
                head = element;
            }
            return element;
        }

        private void setToHead(Element element){
            checkLinkedList();
            if(element == null){
                throw new NullPointerException("空element不能放到linkedlist头部！");
            }
            if(head != null && head != element){
                element.rigth = head;
                head.left = element;
                element.left = null;
            }
            head = element;
        }
        private Element removeTail(){
            checkLinkedList();
            if(tail == null){
                throw new NullPointerException("空lrucache,不能删除尾部！");
            }
            return remove(tail);
        }

        private void checkLinkedList(){
            if((head == null) ^ (tail == null)){
                throw new RuntimeException("lrucache 的 linkedlist 中的head和tail要么同时为空，要么同时不为空");
            }
        }
    }

    LinkedList elements;
    Map<K,Element> elementMap;
    int capacity;
    int size;

    public LRUCache(int capacity){
        elementMap = new HashMap<K, Element>(capacity);
        elements = new LinkedList();
        this.capacity = capacity;
    }

    public V get(K key){
        if(elementMap.containsKey(key)){
            Element keyElement = elementMap.get(key);
            elements.remove(keyElement);
            elements.setToHead(keyElement);
            return keyElement.value;
        }else{
            return null;
        }

    }

    public void put(K key,V value){
        if(elementMap.containsKey(key)){
            Element keyElement = elementMap.get(key);
            elements.setToHead(keyElement);
        }else{
            Element element = elements.addToHead(key,value);
            if (size == capacity){
                Element remEle = elements.removeTail();
                elementMap.remove(remEle.key);
            }else{
                size ++;
            }
            elementMap.put(key,element);
        }
    }


    public static void main(String[] args){
        LRUCache<Integer,Integer> cache = new LRUCache<>( 2 );

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));       // returns 1
        cache.put(3, 3);    // evicts key 2
        System.out.println(cache.get(2));       // returns -1 (not found)
        cache.put(4, 4);    // evicts key 1
        System.out.println(cache.get(1));       // returns -1 (not found)
        System.out.println(cache.get(3));        // returns 3
        System.out.println(cache.get(4));        // returns 4
    }

}
